package graph.base.mingeneratetree;

import graph.graphtype.NoDirectWeightGraph;

/**
 * @author: 26233
 * @create: 2021-11-15 22:24:49
 * @Description
 * graph最小生成树算法Kruskal (加边法)
 * 原理：
 *  1、按weight从小到大排序边关系Nx->Ny，n个节点最终应该有n-1条边
 *  2、从小到大开始选取边关系Nx->Ny
 *  3、判断节点Nx和Ny是否在同一个集合中（可以使用并查集来做）
 *      如果不在同一集合，则合并Nx和Ny，并且边数量cn++
 *      如果在同一集合则可以跳过
 *  4、判断cn是否等于n-1，如果不等于则重复3
 *
 *
 **/

public class Kruskal {

    int[][] edge;
    int nodeCount;
    int[] s;


    public Kruskal(int[][] edge, int nodeCount) {
        this.edge = edge;
        this.nodeCount = nodeCount;
        s = new int[nodeCount];
        for(int i = 0; i < nodeCount; i++){
            s[i] = i;
        }

    }

    public void kruskal(){

        sortEdge(edge);
        for (int i = 0; i < edge.length; i++){

            int[] cur = edge[i];
            union(cur[0], cur[1]);

            System.out.println("select: " + cur[0] + " -> " + cur[1] + ", weight: " + cur[2]);

            if(i == nodeCount - 2){
                break;
            }

        }


    }

    public int find(int e){
        while (s[e] != e){
            e = find(s[e]);
        }
        return e;
    }
    public void union(int e1, int e2){
        int r1 = find(e1);
        int r2 = find(e2);
        s[r2] = r1;

    }

    public void sortEdge(int[][] edge){

        for (int i = 0; i < edge.length; i++){
            for (int j = i; j > 0; j--){

                if (edge[j][2] < edge[j - 1][2]){
                    int[] temp = edge[j];
                    edge[j] = edge[j - 1];
                    edge[j - 1] = temp;
                }

            }
        }

    }

    public static void main(String[] args) {

        int[][] edges = new int[][]{{0, 1, 3}, {0, 2, 5}, {0, 4, 1},
                {1, 3, 1}, {2, 3, 2}, {2, 4, 4},
                {3, 4, 3}};
        int[] data = new int[]{1, 2, 3, 4, 5};
        NoDirectWeightGraph g = new NoDirectWeightGraph(data.length, data);
        g.generateGraphBySingle(edges);

        new Kruskal(edges, 5).kruskal();
    }

}
